﻿namespace Leetcode.N0126;
public class Solution
{
    public IList<IList<string>> FindLadders(string beginWord, string endWord, IList<string> wordList)
    {
        return new SolutionFindLaddersBFS(beginWord, endWord, wordList).FindLadders();

    }

    private class SolutionFindLaddersBFS
    {
        private readonly string beginWord;
        private readonly string endWord;

        // 单词列表
        private readonly IList<string> wordList;

        private readonly string[] subWordsOfEndWord;

        // 子单词来源于哪些单词列表中的单词
        private readonly IDictionary<string, IList<int>> dicSubWords;

        // 每个单词的子单词
        private readonly IDictionary<int, string[]> dicWordListSubWords;

        // 已经查询过的字单词
        private readonly IDictionary<string, bool> visitedSubWords;

        private readonly HashSet<string> beginWordSubwords;

        public SolutionFindLaddersBFS(string beginWord, string endWord, IList<string> wordList)
        {

            this.beginWord = beginWord;
            this.endWord = endWord;
            this.wordList = wordList;

            this.dicWordListSubWords = new Dictionary<int, string[]>();
            this.dicSubWords = new Dictionary<string, IList<int>>();
            this.visitedSubWords = new Dictionary<string, bool>();
            this.beginWordSubwords = this.GetSubWords(this.beginWord).ToHashSet();

            for (int i = 0; i < wordList.Count; i++)
            {
                var item = wordList[i];

                var subWords = this.GetSubWords(item);
                if (item == this.endWord)
                {
                    this.subWordsOfEndWord = subWords;
                }

                this.dicWordListSubWords.Add(i, subWords);

                foreach (var subWord in subWords)
                {
                    if (!this.dicSubWords.ContainsKey(subWord))
                    {
                        this.dicSubWords.Add(subWord, new List<int>());
                    }
                    this.dicSubWords[subWord].Add(i);

                    if (!this.visitedSubWords.ContainsKey(subWord))
                    {
                        this.visitedSubWords.Add(subWord, false);
                    }
                }
            }
        }

        public IList<IList<string>> FindLadders()
        {

            var findLadders = new List<IList<string>>();

            if (this.subWordsOfEndWord == null)
            {
                return findLadders;
            }

            var queue = new Queue<(string subWord, WordPath words)>();


            foreach (var subWord in this.subWordsOfEndWord)
            {
                queue.Enqueue((subWord, new WordPath(this.endWord)));
            }

            bool finded = false;
            while (queue.Count > 0 && finded == false)
            {
                var listSubWords = new List<(string subWord, WordPath words)>();
                while (queue.Count > 0)
                {
                    listSubWords.Add(queue.Dequeue());
                }

                foreach (var queueItem in listSubWords)
                {
                    if (this.beginWordSubwords.Contains(queueItem.subWord))
                    {
                        finded = true;
                        findLadders.Add(queueItem.words.ToList(this.beginWord));
                    }

                    if (finded)
                    {
                        continue;
                    }

                    this.visitedSubWords[queueItem.subWord] = true;
                    foreach (var wordIndex in this.dicSubWords[queueItem.subWord])
                    {
                        var word = this.wordList[wordIndex];

                        foreach (var nextSubWord in this.dicWordListSubWords[wordIndex])
                        {
                            if (this.visitedSubWords[nextSubWord])
                            {
                                continue;
                            }
                            queue.Enqueue((nextSubWord, new WordPath(word, queueItem.words)));
                        }
                    }
                }

            }

            return findLadders.ToList();
        }

        private string[] GetSubWords(string word)
        {
            var subWords = new string[word.Length];

            for (int i = 0; i < word.Length; i++)
            {
                string subWord;
                if (i == 0)
                {
                    subWord = "*" + word.Substring(1);
                }
                else if (i == word.Length - 1)
                {
                    subWord = word.Substring(0, word.Length - 1) + "*";
                }
                else
                {
                    subWord = word.Substring(0, i) + "*" + word.Substring(i + 1);
                }


                subWords[i] = subWord;
            }
            return subWords;
        }
    }

    private class WordPath
    {
        public string val;
        public WordPath next;
        public WordPath(string val)
        {
            this.val = val;
        }

        public WordPath(string val, WordPath next)
        {
            this.val = val;
            this.next = next;
        }

        public IList<string> ToList(string beginWord)
        {
            var list = new List<string>();
            list.Add(beginWord);
            var current = this;
            while (current != null)
            {
                list.Add(current.val);
                current = current.next;
            }
            return list;
        }

    }
}
